Running Time

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Analysis of Algorithms #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

Quantifying execution time.

◇Key Concepts

Goal Focus Approximation Model of Computation Assumptions

◇Details / Theory

Quantifying execution time. - Goal: To measure or predict the time an algorithm takes to execute as a function of ◇Input Size. - Focus: Primarily on how running time increases with n. (Handout 01, Page 3) - Approximation: Exact behavior prediction is difficult; analysis provides an approximation or characterizes the ◇Order of Growth. (Handout 01, Page 3) - Model of Computation: ◇RAM Model - Assumptions: (Handout 02, Page 2) - Generic single-processor machine. - Instructions execute sequentially (no parallelism/concurrency). - Basic instructions (arithmetic, data movement, control flow, comparisons) take constant time (1 time unit). - Memory access (read/write) takes constant time. - Unlimited memory (usually assumed, though space complexity analyzes this). - Limitations: Doesn't account for memory hierarchy (caches, virtual memory), pipelining, multi-core processors, or complex instruction costs. Still useful for comparing algorithms at a high level.

◇Complexity

◇Common Pitfalls

Trying to predict exact running time from analysis — analysis gives an approximation of growth. Forgetting RAM model limitations (no cache, no parallelism in the model).

◇Summary

TL;DR — Running time measures how long an algorithm takes as a function of input size $n$, analyzed under the RAM model where basic operations cost $O(1)$. Focus is on the order of growth, not exact time.

◇Links

Related: - ◇Input Size - ◇Order of Growth - ◇RAM Model Source / Reference:

◇References & Navigation

• Previous Topic: ◇Recursion Tree Method
• Next Topic: ◇Space Complexity
• Related Notes: ◇Algorithm Analysis, ◇Core Concepts